class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        def build(p):
            tokens = [c for c in p if c != '*']
            stars = []
            for c in p:
                if c == '*':
                    stars[-1] = True
                else:
                    stars.append(False)
            tokens.insert(0, '')
            stars.insert(0, False)

            edges = [[] for _ in range(len(tokens))]
            for i in range(len(tokens) - 1):
                j = i + 1
                if stars[j]:
                    edges[i].append([j, ''])
                    edges[j].append([j, tokens[j]])
                else:
                    edges[i].append([j, tokens[j]])
            return edges

        def match(edges, s):
            nodes = {0}

            def search_eps(edges, node):
                eps_nodes = set()
                for v, label in edges[node]:
                    if label == '':
                        eps_nodes.update(search_eps(edges, v))
                        eps_nodes.add(v)
                return eps_nodes

            def transfer_eps(edges, nodes):
                eps_nodes = set()
                for u in nodes:
                    eps_nodes.update(search_eps(edges, u))
                nodes.update(eps_nodes)

            for c in s:
                transfer_eps(edges, nodes)
                new_nodes = set()
                for u in nodes:
                    for v, label in edges[u]:
                        if label == '.' or label == c:
                            new_nodes.add(v)
                nodes = new_nodes
            transfer_eps(edges, nodes)

            return len(edges) - 1 in nodes

        return match(build(p), s)


solution = Solution()


res = solution.isMatch('a', 'ab*')
print(res)


res = solution.isMatch('aab', 'c*a*b')
print(res)

res = solution.isMatch('aaabedfc', 'a*.b.*..c')
print(res)

res = solution.isMatch( 'aabbddc', 'a*.b.*..c')
print(res)

res = solution.isMatch('......', 'a*.b')
print(res)

